翻訳と辞書 Words near each other ・ Sumner Strait ・ Sumner Township ・ Sumner Township, Buchanan County, Iowa ・ Sumner Township, Fillmore County, Minnesota ・ Sumner Township, Illinois ・ Sumner Township, Iowa County, Iowa ・ Sumner Township, Kankakee County, Illinois ・ Sumner Township, Michigan ・ Sumner Township, Warren County, Illinois ・ Sumner Township, Webster County, Iowa ・ Sumner Township, Winneshiek County, Iowa ・ Sumner Tunnel ・ Sumner Twiss ・ Sumner Welles ・ Sumner White ・ Sumner's conjecture ・ Sumner, Barron County, Wisconsin ・ Sumner, Florida ・ Sumner, Georgia ・ Sumner, Illinois ・ Sumner, Iowa ・ Sumner, Jefferson County, Wisconsin ・ Sumner, Maine ・ Sumner, Mississippi ・ Sumner, Missouri ・ Sumner, Nebraska ・ Sumner, New Zealand ・ Sumner, Oklahoma ・ Sumner, Oregon ・ Sumner, Portland, Oregon Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Sumner's conjecture ： ウィキペディア英語版 Sumner's conjecture David Sumner (a graph theorist at the University of South Carolina) conjectured in 1971 that tournaments are universal graphs for polytrees. More precisely, Sumner's conjecture (also called Sumner's universal tournament conjecture) states that every orientation of every $n$-vertex tree is a subgraph of every $(2n-2)$-vertex tournament.〔. However the earliest published citations given by Kühn et al. are to and . cites the conjecture as an undated private communication by Sumner.〕 The conjecture remains unproven; call it "one of the most well-known problems on tournaments." ==Examples== Let polytree $P$ be a star $K\_$, in which all edges are oriented outward from the central vertex to the leaves. Then, $P$ cannot be embedded in the tournament formed from the vertices of a regular $2n-3$-gon by directing every edge clockwise around the polygon. For, in this tournament, every vertex has indegree and outdegree equal to $n-2$, while the central vertex in $P$ has larger outdegree $n-1$.〔This example is from .〕 Thus, if true, Sumner's conjecture would give the best possible size of a universal graph for polytrees. However, in every tournament of $2n-2$ vertices, the average outdegree is $n-\backslash frac$, and the maximum outdegree is an integer greater than or equal to the average. Therefore, there exists a vertex of outdegree $\backslash left\backslash lceil\; n-\backslash frac\backslash right\backslash rceil=n-1$, which can be used as the central vertex for a copy of $P$. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Sumner's conjecture」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.